- Title
- SDGP: a developmental approach for traveling salesman problems
- Creator
- Ouyang, Jin; Weise, Thomas; Devert, Alexandre; Chiong, Raymond
- Relation
- 2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS). Proceedings of the 2013 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS) (Singapore 16-19 April, 2013) p. 78-85
- Publisher Link
- http://dx.doi.org/10.1109/CIPLS.2013.6595203
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2013
- Description
- This paper presents an Evolutionary Algorithm using a new ontogenic approach, called Staged Developmental Genetic Programming (SDGP), for solving symmetric Traveling Salesman Problems (TSPs). In SDGP, a genotype-phenotype mapping (gpm) is used to refine candidate solutions to a TSP - these candidate solutions are represented as permutations. The gpm performs several development steps, in each of which such a permutation x is incrementally modified. In each iteration within a development step, the process can choose to either apply one of seven different modifications to a specific section of x or do nothing. The choice is made by the genotypes g, which are functions assigning real-valued ratings to the possible modifications. Smaller ratings are better and the best-rated modification is then applied, if its rating is lower than a given threshold. The genotypes are evolved using tree-based Genetic Programming. Comprehensive numerical simulation experiments show that our proposed algorithm scales well with the problem size and delivers competitive results compared to other state-of-the-art approaches in the TSP literature.
- Subject
- staged developmental genetic programming; evolutionary algorithm; symmetric traveling salesman problems
- Identifier
- http://hdl.handle.net/1959.13/1057777
- Identifier
- uon:16263
- Identifier
- ISBN:9781467359054
- Language
- eng
- Reviewed
- Hits: 1793
- Visitors: 1772
- Downloads: 1
Thumbnail | File | Description | Size | Format |
---|